package leeon.mobile.server.bbscache.entity;

import java.io.Serializable;
import java.util.ArrayList;
import java.util.List;

/**
 * 构造一个查询用的offset索引
 * 可以缓存起来，将start转化为 offset
 * @author study
 *
 */
public class OffsetIndex implements Serializable{
	
	private static final long serialVersionUID = 5806831498508465854L;

	private List<Integer> key = new ArrayList<Integer>();
	private List<Long> value = new ArrayList<Long>();
	private static final long MIN_VALUE = 0L;
	private static final long MAX_VALUE = Long.MAX_VALUE;
	
	public OffsetIndex() {
		key.add(-1);value.add(MIN_VALUE);
		key.add(0);value.add(MAX_VALUE);
	}
	
	public void removeFromIndex(long v) {
		if (v < MIN_VALUE || v >= MAX_VALUE) return;
		
		int lastI = -1;
		long lastV = MIN_VALUE;
		boolean dealed = false;
		for (int i = 0; i < key.size(); i ++) {
			int currentI = key.get(i);
			long currentV = value.get(i);
			
			if (dealed) {
				key.set(i, currentI-1);//已经处理过了的都是后面+1
				continue;
			}
			
			if (v >= lastV && v < currentV) {//在两者区间中，需要处理
				long a1 = lastV + (currentI-lastI) - 1;//上一连续段最后一值
				if (v == lastV && lastV == a1) {//单个节点
					key.remove(i-1);
					value.remove(i-1);//去掉，后面-1
					i-=2;
				} else if (v == lastV && v < a1) {//第一个节点
					value.set(i-1, v+1);
					i--;
					//改写当前，随后面-1
				} else if (v > lastV && v < a1) {//中间节点
					key.add(i, (int)(v-lastV)+lastI);
					value.add(i, v+1);
					//插入节点，随后面-1
				} else if (v > lastV && v == a1) {//最后一个节点
					//后面+1
					i--;
				}
				dealed = true;
			}//剩余就只有value >= current的情况，在下一次循环中处理
			lastI = currentI;
			lastV = currentV;			
		}
	}
	
	public void addToIndex(long v) {
		if (v < MIN_VALUE || v >= MAX_VALUE) return;
		
		int lastI = -1;
		long lastV = MIN_VALUE;
		boolean dealed = false;
		for (int i = 0; i < key.size(); i ++) {
			int currentI = key.get(i);
			long currentV = value.get(i);
			
			if (dealed) {
				key.set(i, currentI+1);//已经处理过了的都是后面+1
				continue;
			}
			
			if (v == lastV) return;//有重复值，不处理
			else if (v > lastV && v < currentV) {//在两者区间中，需要处理
				long a1 = lastV + (currentI-lastI);//上一连续段后一值
				long a2 = currentV - 1;//下一连续段前一值
				if (v < a1 ) {//和前连续段重复
					return;
				} else if (v == a1 && a1 == a2) {//恰好为前后连续段中间一值
					key.remove(i);
					value.remove(i--);
					//去掉当前，随后后面+1
				} else if (v == a1 && v < a2) {//加入前连续段
					key.set(i, currentI+1);
					//后面+1
				} else if (v > a1 && v < a2) {//和前后都不连续
					key.add(i, currentI);
					value.add(i, v);
					//在currentI前插入value，当前currentI不去掉，后面+1
				} else if (v > a1 && v == a2) {//加入后连续段
					value.set(i, v);
					//改写当前currentI为value，当前currentI去掉，后面+1
				}
				dealed = true;
			}//剩余就只有value >= current的情况，在下一次循环中处理
			lastI = currentI;
			lastV = currentV;			
		}
	}
	
	//return -1表示没有找到
	public long getValue(int offset) {
		if (offset < 0) return -1;
		
		int lastI = -1;
		long lastV = MIN_VALUE;
		for (int i = 0; i < key.size(); i ++) {
			int currentI = key.get(i);
			long currentV = value.get(i);
			
			if (offset == currentI && i != key.size()-1) return currentV;
			else if (offset > lastI && offset < currentI) {
				return lastV + (offset-lastI);
			}
			lastI = currentI;
			lastV = currentV;
		}
		return -1;
	}
	
	//通过值拿到offset
	public int getOffset(long v) {
		if (v <= MIN_VALUE || v >= MAX_VALUE) return -1;
		int lastI = -1;
		long lastV = MIN_VALUE;
		for (int i = 0; i < key.size(); i ++) {
			int currentI = key.get(i);
			long currentV = value.get(i);
			if (v >= lastV && v < lastV + (currentI-lastI)) {
				return lastI + (int)(v-lastV);
			} else if (v < currentV) {
				return -1;
			}
			lastI = currentI;
			lastV = currentV;
		}
		return -1;
	}
	
	//某个值的前一个值
	public long previous(long value) {
		int offset = getOffset(value);
		if (offset <= 0) return -1L;
		else return getValue(offset-1);
	}
	
	//某个值的后一个值
	public long next(long value) {
		int offset = getOffset(value);
		if (offset >= (size()-1) || offset == -1) return -1L;
		else return getValue(offset+1);
	}
	
	//最后一个key值
	public long last() {
		return getValue(size()-1);
	}
	
	//第一个key值
	public long first() {
		return getValue(0);
	}
	
	//总记录数
	public int size() {
		return key.get(key.size()-1);
	}
	
	public boolean isEmpty() {
		return (key.size() <= 2);
	}
	
	public void print() {
		for (int i = 0; i < key.size(); i ++) {
			System.out.println(key.get(i) + ":" + value.get(i));
		}
	}
	
	public String toString() {
		StringBuffer sb = new StringBuffer();
		for (int i = 0; i < key.size(); i ++) {
			sb.append(key.get(i) + ":" + value.get(i) + "\n");
		}
		return sb.toString();
	}

	public static void main(String[] a) {
		OffsetIndex index = new OffsetIndex();
		index.addToIndex(1001);
		index.addToIndex(1002);
		index.addToIndex(1003);
		index.addToIndex(1008);
		index.addToIndex(1010);
		index.addToIndex(1011);
		index.addToIndex(1023);
		
		index.addToIndex(1027);
		index.addToIndex(1028);
		
		index.addToIndex(1004);//加入前连续段
		index.addToIndex(1009);//恰好为前后连续段中间一值
		index.addToIndex(1020);//和前后都不连续
		index.addToIndex(1026);//加入后连续段
		
		index.print();
		
		/**
		index.removeFromIndex(1027);//移除中间
		index.removeFromIndex(1020);//移除单个
		
		index.removeFromIndex(1001);//移除第一个
		index.removeFromIndex(1004);//移除最后
		index.removeFromIndex(2000);//no exists
		
		index.removeFromIndex(1003);
		index.removeFromIndex(1002);
		index.removeFromIndex(1010);
		index.removeFromIndex(1011);
		index.removeFromIndex(1009);
		index.removeFromIndex(1008);
		index.removeFromIndex(1028);
		index.removeFromIndex(1026);
		index.removeFromIndex(1023);
		index.print();
		**/
		
		System.out.println(index.getValue(0));
		System.out.println(index.getValue(1));
		System.out.println(index.getValue(2));
		System.out.println(index.getValue(3));
		System.out.println(index.getValue(4));
		System.out.println(index.getValue(5));
		System.out.println(index.getValue(6));
		System.out.println(index.getValue(7));
		System.out.println(index.getValue(8));
		System.out.println(index.getValue(9));
		System.out.println(index.getValue(10));
		System.out.println(index.getValue(11));
		System.out.println(index.getValue(12));
		System.out.println(index.getValue(13));
		System.out.println(index.getValue(14));
		
		System.out.println(index.getOffset(1000));
		System.out.println(index.getOffset(1001));
		System.out.println(index.getOffset(1002));
		System.out.println(index.getOffset(1003));
		System.out.println(index.getOffset(1008));
		System.out.println(index.getOffset(1009));
		
		System.out.println(index.first());
		System.out.println(index.last());
		System.out.println(index.size());
		
		System.out.println(index.previous(1008));
		System.out.println(index.previous(1004));
		System.out.println(index.next(1004));
		System.out.println(index.next(1008));
		
		System.out.println(index.previous(1002));
		System.out.println(index.previous(1001));
		System.out.println(index.previous(1000));
		
		System.out.println(index.next(1027));
		System.out.println(index.next(1028));
		System.out.println(index.next(1029));
	}
}
